/*
 ------------------------------------------------------------------------------
 Copyright (C) 2006-2007 Team Blur.

 This file is part of the Quantum Engine source code.

 The Quantum Engine source code is free software; you can redistribute it and/or
 modify it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2 of the License, or (at your
 option) any later version.

 The Quantum Engine source code is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 more details.

 You should have received a copy of the GNU General Public License along with
 the Quantum Engine source code; if not, write to the Free Software Foundation, Inc.,
 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 ------------------------------------------------------------------------------
*/


#include "r_local.h"


#define LIGHT_PARALLEL_DISTANCE			1099511627776.0f

#define MAX_LIGHT_PLANE_POINTS			32

typedef struct {
	bool				degenerate;

	odPlane				frustum[5];
} nearClipVolume_t;

static nearClipVolume_t	r_nearClipVolume;

static drawMesh_t		r_interactionMeshes[2][MAX_DRAW_MESHES];
static drawMesh_t		r_shadowMeshes[2][MAX_DRAW_MESHES];


/*
 ==================
 R_CopyCompiledLightData
 ==================
*/
static bool R_CopyCompiledLightData (scene_t *scene, light_t *light){

	compiledLight_t	*compiledLight;

	if (light->l.lightNum < 0 || light->l.lightNum >= MAX_ENTITIES)
		return false;	// Should never happen

	compiledLight = scene->compiledLightsList[light->l.lightNum];

	if (!compiledLight)
		return false;	// Not compiled

	// If the render light has changed since compiling the light, the compiled
	// light data is no longer valid.
	// We have a few specific exceptions though: detailLevel, allowInView, and
	// materialParms can change without invalidating the compiled light data.
	if (compiledLight->l.type != light->l.type)
		return false;
	if (compiledLight->l.lightNum != light->l.lightNum)
		return false;
	if (compiledLight->l.origin != light->l.origin)
		return false;
	if (compiledLight->l.center != light->l.center)
		return false;
	if (compiledLight->l.axis != light->l.axis)
		return false;
	if (compiledLight->l.radius != light->l.radius)
		return false;
	if (compiledLight->l.fovX != light->l.fovX)
		return false;
	if (compiledLight->l.fovY != light->l.fovY)
		return false;
	if (compiledLight->l.falloffRange != light->l.falloffRange)
		return false;
	if (compiledLight->l.parallel != light->l.parallel)
		return false;
	if (compiledLight->l.noShadows != light->l.noShadows)
		return false;
	if (compiledLight->l.material != light->l.material)
		return false;

	// The render light hasn't changed, so copy the compiled light data
	light->data = compiledLight->data;

	return true;
}

/*
 ==================
 R_SetupLightData
 ==================
*/
static void R_SetupLightData (scene_t *scene, light_t *light, material_t *lightMaterial, bool inWorld){

	int		cornerIndices[6][3] = {{6, 2, 3}, {5, 1, 0}, {1, 3, 2}, {7, 5, 4}, {7, 3, 1}, {4, 0, 2}};
	node_t	*leaf;
	odPlane	*plane;
	odMat3	axis[2];
	odVec3	dir, tmp;
	float	x, y;
	int		i;

	if (light->data.computed)
		return;		// Already computed the light data

	// If the light data was compiled, copy it and return immediately
	if (R_CopyCompiledLightData(scene, light))
		return;

	// Compute the origin
	if (light->l.parallel){
		dir = light->l.center;
		dir.NormalizeFast();

		light->l.axis.UnprojectVector(dir * LIGHT_PARALLEL_DISTANCE, light->data.origin);
	}
	else {
		light->l.axis.UnprojectVector(light->l.center, light->data.origin);
		light->data.origin += light->l.origin;
	}

	// Compute the bounding volume
	if (light->l.type == RL_POINT){
		// Compute the corner points
		for (i = 0; i < 8; i++){
			tmp[0] = (i & 1) ? -light->l.radius[0] : light->l.radius[0];
			tmp[1] = (i & 2) ? -light->l.radius[1] : light->l.radius[1];
			tmp[2] = (i & 4) ? -light->l.radius[2] : light->l.radius[2];

			// Transform into world space
			light->l.axis.UnprojectVector(tmp, light->data.corners[i]);
			light->data.corners[i] += light->l.origin;
		}

		// Compute the frustum planes
		for (i = 0, plane = light->data.frustum; i < 6; i++, plane++){
			if (i & 1){
				plane->normal = -light->l.axis[i>>1];
				plane->dist = -light->l.origin.Dot(light->l.axis[i>>1]) - light->l.radius[i>>1];
			}
			else {
				plane->normal = light->l.axis[i>>1];
				plane->dist = light->l.origin.Dot(light->l.axis[i>>1]) - light->l.radius[i>>1];
			}

			plane->SetType();
			plane->SetSignBits();
		}
	}
	else {
		// Compute the corner points
		x = M_Tan(light->l.fovX * (M_PI / 360.0f));
		y = M_Tan(light->l.fovY * (M_PI / 360.0f));

		axis[0][0] = light->l.axis[0] * x;
		axis[0][1] = light->l.axis[1] * y;
		axis[0][2] = light->l.axis[2];

		axis[1][0] = light->l.axis[0] * light->l.falloffRange * x;
		axis[1][1] = light->l.axis[1] * light->l.falloffRange * y;
		axis[1][2] = light->l.axis[2] * light->l.falloffRange;

		light->data.corners[0] = light->l.origin + axis[1][0] + axis[1][1] + axis[1][2];
		light->data.corners[1] = light->l.origin - axis[1][0] + axis[1][1] + axis[1][2];
		light->data.corners[2] = light->l.origin + axis[1][0] - axis[1][1] + axis[1][2];
		light->data.corners[3] = light->l.origin - axis[1][0] - axis[1][1] + axis[1][2];
		light->data.corners[4] = light->l.origin + axis[0][0] + axis[0][1] + axis[0][2];
		light->data.corners[5] = light->l.origin - axis[0][0] + axis[0][1] + axis[0][2];
		light->data.corners[6] = light->l.origin + axis[0][0] - axis[0][1] + axis[0][2];
		light->data.corners[7] = light->l.origin - axis[0][0] - axis[0][1] + axis[0][2];

		// Compute the frustum planes
		for (i = 0, plane = light->data.frustum; i < 6; i++, plane++){
			plane->Set(light->data.corners[cornerIndices[i][0]], light->data.corners[cornerIndices[i][1]], light->data.corners[cornerIndices[i][2]]);
			plane->SetType();
			plane->SetSignBits();
		}
	}

	// Compute the fog plane or transformation matrices
	if (lightMaterial->lightType == LT_FOG){
		light->data.planeNormal.Cross(light->data.corners[1] - light->data.corners[2], light->data.corners[3] - light->data.corners[2]);
		light->data.planeNormal.Normalize();

		light->data.planeDist = light->data.corners[0].Dot(light->data.planeNormal);
	}
	else {
		if (light->l.type == RL_POINT){
			light->data.projectionMatrix[0][0] = 0.5f / light->l.radius[0];
			light->data.projectionMatrix[0][1] = 0.0f;
			light->data.projectionMatrix[0][2] = 0.0f;
			light->data.projectionMatrix[0][3] = 0.0f;
			light->data.projectionMatrix[1][0] = 0.0f;
			light->data.projectionMatrix[1][1] = 0.5f / light->l.radius[1];
			light->data.projectionMatrix[1][2] = 0.0f;
			light->data.projectionMatrix[1][3] = 0.0f;
			light->data.projectionMatrix[2][0] = 0.0f;
			light->data.projectionMatrix[2][1] = 0.0f;
			light->data.projectionMatrix[2][2] = 0.5f / light->l.radius[2];
			light->data.projectionMatrix[2][3] = 0.0f;
			light->data.projectionMatrix[3][0] = 0.5f;
			light->data.projectionMatrix[3][1] = 0.5f;
			light->data.projectionMatrix[3][2] = 0.5f;
			light->data.projectionMatrix[3][3] = 1.0f;
		}
		else {
			light->data.projectionMatrix[0][0] = -0.5f / M_Tan(light->l.fovX * (M_PI / 360.0f));
			light->data.projectionMatrix[0][1] = 0.0f;
			light->data.projectionMatrix[0][2] = 0.0f;
			light->data.projectionMatrix[0][3] = 0.0f;
			light->data.projectionMatrix[1][0] = 0.0f;
			light->data.projectionMatrix[1][1] = -0.5f / M_Tan(light->l.fovY * (M_PI / 360.0f));
			light->data.projectionMatrix[1][2] = 0.0f;
			light->data.projectionMatrix[1][3] = 0.0f;
			light->data.projectionMatrix[2][0] = -0.5f;
			light->data.projectionMatrix[2][1] = -0.5f;
			light->data.projectionMatrix[2][2] = 1.0f / light->l.falloffRange;
			light->data.projectionMatrix[2][3] = -1.0f;
			light->data.projectionMatrix[3][0] = 0.0f;
			light->data.projectionMatrix[3][1] = 0.0f;
			light->data.projectionMatrix[3][2] = 0.0f;
			light->data.projectionMatrix[3][3] = 0.0f;
		}

		light->data.modelviewMatrix[0][0] = light->l.axis[0][0];
		light->data.modelviewMatrix[0][1] = light->l.axis[1][0];
		light->data.modelviewMatrix[0][2] = light->l.axis[2][0];
		light->data.modelviewMatrix[0][3] = 0.0f;
		light->data.modelviewMatrix[1][0] = light->l.axis[0][1];
		light->data.modelviewMatrix[1][1] = light->l.axis[1][1];
		light->data.modelviewMatrix[1][2] = light->l.axis[2][1];
		light->data.modelviewMatrix[1][3] = 0.0f;
		light->data.modelviewMatrix[2][0] = light->l.axis[0][2];
		light->data.modelviewMatrix[2][1] = light->l.axis[1][2];
		light->data.modelviewMatrix[2][2] = light->l.axis[2][2];
		light->data.modelviewMatrix[2][3] = 0.0f;
		light->data.modelviewMatrix[3][0] = -light->l.origin.Dot(light->l.axis[0]);
		light->data.modelviewMatrix[3][1] = -light->l.origin.Dot(light->l.axis[1]);
		light->data.modelviewMatrix[3][2] = -light->l.origin.Dot(light->l.axis[2]);
		light->data.modelviewMatrix[3][3] = 1.0f;
	}

	// Set up the PVS and area
	if (inWorld){
		leaf = R_PointInLeaf(light->data.origin);

		if (leaf->cluster == -1 || leaf->area == -1){
			light->data.pvs = NULL;
			light->data.area = -1;
		}
		else {
			light->data.pvs = CM_ClusterPVS(leaf->cluster);
			light->data.area = leaf->area;
		}
	}
	else {
		light->data.pvs = NULL;
		light->data.area = -1;
	}

	// Clear precompiled interactions and shadows
	light->data.precompiled = false;

	light->data.interactionNodes = NULL;
	light->data.shadowNodes = NULL;

	// The necessary light data has been computed
	light->data.computed = true;
}


/*
 ==============================================================================

 INTERACTION & SHADOW CULLING

 ==============================================================================
*/


/*
 ==================
 R_LightCullBounds

 Returns cullBits, or CULL_OUT if completely outside the frustum
 ==================
*/
static int R_LightCullBounds (lightData_t *data, const odBounds &bounds, int planeBits){

	odPlane	*plane;
	int		side, cullBits;
	int		i;

	cullBits = 0;

	// Check against frustum planes
	for (i = 0, plane = data->frustum; i < 6; i++, plane++){
		if (!(planeBits & BIT(i)))
			continue;

		side = plane->BoundsOnSide(bounds);

		if (side == PLANESIDE_BACK){
			tr.pc.cullOut++;
			return CULL_OUT;
		}

		if (side == PLANESIDE_CROSS)
			cullBits |= BIT(i);
	}

	if (cullBits)
		tr.pc.cullClip++;
	else
		tr.pc.cullIn++;

	return cullBits;
}

/*
 ==================
 R_LightCullEntityBounds

 Returns cullBits, or CULL_OUT if completely outside the frustum
 ==================
*/
static int R_LightCullEntityBounds (lightData_t *data, const odBounds &bounds, int planeBits, entity_t *entity){
 
	odPlane	*plane;
	odVec3	corners[8], tmp;
	int		side, cullBits;
	int		i, j;

	cullBits = 0;

	// Compute the corner points of the bounding volume
	for (i = 0; i < 8; i++){
		tmp[0] = (i & 1) ? bounds[0][0] : bounds[1][0];
		tmp[1] = (i & 2) ? bounds[0][1] : bounds[1][1];
		tmp[2] = (i & 4) ? bounds[0][2] : bounds[1][2];

		// Transform into world space
		entity->e.axis.UnprojectVector(tmp, corners[i]);
		corners[i] += entity->e.origin;
	}

	// Check against frustum planes
	for (i = 0, plane = data->frustum; i < 6; i++, plane++){
		if (!(planeBits & BIT(i)))
			continue;

		side = 0;

		for (j = 0; j < 8; j++){
			side |= plane->PointOnSide(corners[j]);

			if (side == PLANESIDE_CROSS)
				break;
		}

		if (side == PLANESIDE_BACK){
			tr.pc.cullOut++;
			return CULL_OUT;
		}

		if (side == PLANESIDE_CROSS)
			cullBits |= BIT(i);
	}

	if (cullBits)
		tr.pc.cullClip++;
	else
		tr.pc.cullIn++;

	return cullBits;
}

/*
 ==================
 R_LightCullSphere

 Returns cullBits, or CULL_OUT if completely outside the frustum
 ==================
*/
static int R_LightCullSphere (lightData_t *data, const odVec3 &center, float radius, int planeBits){

	odPlane	*plane;
	int		side, cullBits;
	int		i;

	cullBits = 0;

	// Check against frustum planes
	for (i = 0, plane = data->frustum; i < 6; i++, plane++){
		if (!(planeBits & BIT(i)))
			continue;

		side = plane->SphereOnSide(center, radius);

		if (side == PLANESIDE_BACK){
			tr.pc.cullOut++;
			return CULL_OUT;
		}

		if (side == PLANESIDE_CROSS)
			cullBits |= BIT(i);
	}

	if (cullBits)
		tr.pc.cullClip++;
	else
		tr.pc.cullIn++;

	return cullBits;
}

/*
 ==================
 R_LightCullEntitySphere

 Returns cullBits, or CULL_OUT if completely outside the frustum
 ==================
*/
static int R_LightCullEntitySphere (lightData_t *data, const odVec3 &center, float radius, int planeBits, entity_t *entity){

	odPlane	*plane;
	odVec3	point;
	int		side, cullBits;
	int		i;

	cullBits = 0;

	// Transform into world space
	entity->e.axis.UnprojectVector(center, point);
	point += entity->e.origin;

	// Check against frustum planes
	for (i = 0, plane = data->frustum; i < 6; i++, plane++){
		if (!(planeBits & BIT(i)))
			continue;

		side = plane->SphereOnSide(point, radius);

		if (side == PLANESIDE_BACK){
			tr.pc.cullOut++;
			return CULL_OUT;
		}

		if (side == PLANESIDE_CROSS)
			cullBits |= BIT(i);
	}

	if (cullBits)
		tr.pc.cullClip++;
	else
		tr.pc.cullIn++;

	return cullBits;
}

/*
 ==================
 R_LightCullShadow

 Returns cullBits, or CULL_OUT if completely outside the frustum
 ==================
*/
static bool R_LightCullShadow (lightData_t *data, const odBounds &bounds, int planeBits){

	odPlane	*plane;
	odVec3	corners[16];
	int		side, cullBits;
	int		i, j;

	cullBits = 0;

	// Compute the corner points of the bounding volume
	for (i = 0; i < 8; i++){
		corners[i][0] = (i & 1) ? bounds[0][0] : bounds[1][0];
		corners[i][1] = (i & 2) ? bounds[0][1] : bounds[1][1];
		corners[i][2] = (i & 4) ? bounds[0][2] : bounds[1][2];

		// Project the corner point
		corners[i+8] = corners[i] - data->origin;
	}

	// Check against frustum planes
	for (i = 0, plane = tr.viewParms.frustum; i < 5; i++, plane++){
		if (!(planeBits & BIT(i)))
			continue;

		side = 0;

		for (j = 0; j < 8; j++){
			if (plane->normal.Dot(corners[j]) > plane->dist)
				side |= PLANESIDE_FRONT;
			else
				side |= PLANESIDE_BACK;

			if (side == PLANESIDE_CROSS)
				break;

			if (plane->normal.Dot(corners[j+8]) > 0.0f)
				side |= PLANESIDE_FRONT;
			else
				side |= PLANESIDE_BACK;

			if (side == PLANESIDE_CROSS)
				break;
		}

		if (side == PLANESIDE_BACK){
			tr.pc.cullOut++;
			return CULL_OUT;
		}

		if (side == PLANESIDE_CROSS)
			cullBits |= BIT(i);
	}

	if (cullBits)
		tr.pc.cullClip++;
	else
		tr.pc.cullIn++;

	return cullBits;
}

/*
 ==================
 R_LightCullEntityShadow

 Returns cullBits, or CULL_OUT if completely outside the frustum
 ==================
*/
static bool R_LightCullEntityShadow (lightData_t *data, const odBounds &bounds, int planeBits, entity_t *entity){

	odPlane	*plane;
	odVec3	corners[16], tmp;
	odVec3	lightOrigin;
	int		side, cullBits;
	int		i, j;

	cullBits = 0;

	// Transform light origin into world space
	entity->e.axis.UnprojectVector(data->origin, lightOrigin);
	lightOrigin += entity->e.origin;

	// Compute the corner points of the bounding volume
	for (i = 0; i < 8; i++){
		tmp[0] = (i & 1) ? bounds[0][0] : bounds[1][0];
		tmp[1] = (i & 2) ? bounds[0][1] : bounds[1][1];
		tmp[2] = (i & 4) ? bounds[0][2] : bounds[1][2];

		// Transform into world space
		entity->e.axis.UnprojectVector(tmp, corners[i]);
		corners[i] += entity->e.origin;

		// Project the corner point
		corners[i+8] = corners[i] - lightOrigin;
	}

	// Check against frustum planes
	for (i = 0, plane = tr.viewParms.frustum; i < 5; i++, plane++){
		if (!(planeBits & BIT(i)))
			continue;

		side = 0;

		for (j = 0; j < 8; j++){
			if (plane->normal.Dot(corners[j]) > plane->dist)
				side |= PLANESIDE_FRONT;
			else
				side |= PLANESIDE_BACK;

			if (side == PLANESIDE_CROSS)
				break;

			if (plane->normal.Dot(corners[j+8]) > 0.0f)
				side |= PLANESIDE_FRONT;
			else
				side |= PLANESIDE_BACK;

			if (side == PLANESIDE_CROSS)
				break;
		}

		if (side == PLANESIDE_BACK){
			tr.pc.cullOut++;
			return CULL_OUT;
		}

		if (side == PLANESIDE_CROSS)
			cullBits |= BIT(i);
	}

	if (cullBits)
		tr.pc.cullClip++;
	else
		tr.pc.cullIn++;

	return cullBits;
}


/*
 ==============================================================================

 NEAR CLIP VOLUME FOR SHADOW CAPS CULLING

 ==============================================================================
*/


/*
 ==================
 R_SetupNearClipVolume
 ==================
*/
static void R_SetupNearClipVolume (const odVec3 &lightOrigin){

	odPlane	*planes = r_nearClipVolume.frustum;
	odMat3	axis;
	odVec3	corners[4];
	odVec3	dir, point;
	float	d1, d2;
	float	x, y;
	int		i, side;

	// See which side of the near plane the light is
	side = tr.viewParms.frustum[4].PointOnSide(lightOrigin, ON_EPSILON);

	// If exactly on the plane, the near clip volume is degenerate
	if (side == PLANESIDE_ON){
		r_nearClipVolume.degenerate = true;
		return;
	}

	r_nearClipVolume.degenerate = false;

	// Compute the world space corner points of the viewport
	x = M_Tan(tr.renderView.fovX * (M_PI / 360.0f));
	y = M_Tan(tr.renderView.fovY * (M_PI / 360.0f));

	axis[0] = tr.renderView.axis[0] * r_zNear->floatValue;
	axis[1] = tr.renderView.axis[1] * r_zNear->floatValue * x;
	axis[2] = tr.renderView.axis[2] * r_zNear->floatValue * y;

	corners[0] = tr.renderView.origin + axis[0] - axis[1] + axis[2];
	corners[1] = tr.renderView.origin + axis[0] + axis[1] + axis[2];
	corners[2] = tr.renderView.origin + axis[0] + axis[1] - axis[2];
	corners[3] = tr.renderView.origin + axis[0] - axis[1] - axis[2];

	// If the near plane is sheared, we need to expand the viewport
	if (tr.viewParms.viewType == VIEW_MIRROR || tr.viewParms.viewType == VIEW_PORTAL){
		for (i = 0; i < 4; i++){
			dir = corners[i] - tr.renderView.origin;
			dir.NormalizeFast();

			point = corners[i] + dir * 1048576.0f;

			d1 = tr.viewParms.frustum[4].Distance(point);
			d2 = tr.viewParms.frustum[4].Distance(corners[i]);

			if (d1 == d2)
				continue;

			corners[i].Lerp(corners[i], point, d1 / (d1 - d2));
		}
	}

	// Set up the frustum planes
	if (side == PLANESIDE_FRONT){
		planes[0].Set(lightOrigin, corners[1], corners[0]);
		planes[1].Set(lightOrigin, corners[2], corners[1]);
		planes[2].Set(lightOrigin, corners[3], corners[2]);
		planes[3].Set(lightOrigin, corners[0], corners[3]);
		planes[4].Set(tr.viewParms.frustum[4].normal, tr.viewParms.frustum[4].dist);
	}
	else {
		planes[0].Set(lightOrigin, corners[0], corners[1]);
		planes[1].Set(lightOrigin, corners[1], corners[2]);
		planes[2].Set(lightOrigin, corners[2], corners[3]);
		planes[3].Set(lightOrigin, corners[3], corners[0]);
		planes[4].Set(-tr.viewParms.frustum[4].normal, -tr.viewParms.frustum[4].dist);
	}

	for (i = 0; i < 5; i++){
		planes[i].SetType();
		planes[i].SetSignBits();
	}
}

/*
 ==================
 R_ShadowInNearClipVolume
 ==================
*/
static bool R_ShadowInNearClipVolume (const odBounds &bounds){

	odPlane	*plane;
	int		i;

	// If degenerate, just check if the near plane is intersected
	if (r_nearClipVolume.degenerate){
		if (tr.viewParms.frustum[4].BoundsOnSide(bounds) != PLANESIDE_CROSS)
			return false;

		return true;
	}

	// Check against frustum planes
	for (i = 0, plane = r_nearClipVolume.frustum; i < 5; i++, plane++){
		if (plane->BoundsOnSide(bounds) == PLANESIDE_BACK)
			return false;
	}

	return true;
}

/*
 ==================
 R_EntityShadowInNearClipVolume
 ==================
*/
static bool R_EntityShadowInNearClipVolume (const odBounds &bounds, entity_t *entity){

	odPlane	*plane;
	odVec3	corners[8], tmp;
	int		side;
	int		i, j;

	// Compute the corner points of the bounding volume
	for (i = 0; i < 8; i++){
		tmp[0] = (i & 1) ? bounds[0][0] : bounds[1][0];
		tmp[1] = (i & 2) ? bounds[0][1] : bounds[1][1];
		tmp[2] = (i & 4) ? bounds[0][2] : bounds[1][2];

		// Transform into world space
		entity->e.axis.UnprojectVector(tmp, corners[i]);
		corners[i] += entity->e.origin;
	}

	// If degenerate, just check if the near plane is intersected
	if (r_nearClipVolume.degenerate){
		side = 0;

		for (j = 0; j < 8; j++){
			side |= tr.viewParms.frustum[4].PointOnSide(corners[j]);

			if (side == PLANESIDE_CROSS)
				break;
		}

		if (side != PLANESIDE_CROSS)
			return false;

		return true;
	}

	// Check against frustum planes
	for (i = 0, plane = r_nearClipVolume.frustum; i < 5; i++, plane++){
		side = 0;

		for (j = 0; j < 8; j++){
			side |= plane->PointOnSide(corners[j]);

			if (side != PLANESIDE_BACK)
				break;
		}

		if (side == PLANESIDE_BACK)
			return false;
	}

	return true;
}


/*
 ==============================================================================

 SCISSOR RECTANGLE AND DEPTH BOUNDS

 ==============================================================================
*/


/*
 ==================
 R_ClipLightPlane
 ==================
*/
static void R_ClipLightPlane (odBounds &bounds, int numPoints, odVec3 *points, int stage){

	odVec3	clipped[MAX_LIGHT_PLANE_POINTS];
	float	dists[MAX_LIGHT_PLANE_POINTS];
	int		sides[MAX_LIGHT_PLANE_POINTS];
	bool	front, back;
	odVec4	in, out;
	odVec3	point;
	float	scale;
	int		i, numClipped;

	if (stage == 5){
		// Fully clipped, so add points in normalized device coordinates
		for (i = 0; i < numPoints; i++){
			in[0] = points[i][0];
			in[1] = points[i][1];
			in[2] = points[i][2];
			in[3] = 1.0f;

			tr.viewParms.mvpMatrix.ProjectVector(in, out);

			if (out[3] == 0.0f)
				continue;

			scale = 1.0f / out[3];

			point[0] = out[0] * scale;
			point[1] = out[1] * scale;
			point[2] = out[2] * scale;

			bounds.AddPoint(point);
		}

		return;
	}

	if (numPoints > MAX_LIGHT_PLANE_POINTS - 2)
		Com_Error(false, "R_ClipLightPlane: MAX_LIGHT_PLANE_POINTS hit");

	// Determine sides for each point
	front = false;
	back = false;

	for (i = 0; i < numPoints; i++){
		dists[i] = tr.viewParms.frustum[stage].Distance(points[i]);

		if (dists[i] > ON_EPSILON){
			sides[i] = PLANESIDE_FRONT;
			front = true;
			continue;
		}

		if (dists[i] < -ON_EPSILON){
			sides[i] = PLANESIDE_BACK;
			back = true;
			continue;
		}

		sides[i] = PLANESIDE_ON;
	}

	if (!front)
		return;		// Not clipped

	if (!back){
		// Continue
		R_ClipLightPlane(bounds, numPoints, points, stage+1);
		return;
	}

	// Clip it
	points[i] = points[0];

	dists[i] = dists[0];
	sides[i] = sides[0];

	numClipped = 0;

	for (i = 0; i < numPoints; i++){
		if (sides[i] == PLANESIDE_ON){
			clipped[numClipped++] = points[i];
			continue;
		}

		if (sides[i] == PLANESIDE_FRONT)
			clipped[numClipped++] = points[i];

		if (sides[i+1] == PLANESIDE_ON || sides[i+1] == sides[i])
			continue;

		if (dists[i] == dists[i+1])
			clipped[numClipped++] = points[i];
		else
			clipped[numClipped++].Lerp(points[i], points[i+1], dists[i] / (dists[i] - dists[i+1]));
	}

	// Continue
	R_ClipLightPlane(bounds, numClipped, clipped, stage+1);
}

/*
 ==================
 R_ClipLightToScreen
 ==================
*/
static void R_ClipLightToScreen (drawLight_t *drawLight){

	int			cornerIndices[6][4] = {{3, 2, 6, 7}, {0, 1, 5, 4}, {2, 3, 1, 0}, {4, 5, 7, 6}, {1, 3, 7, 5}, {2, 0, 4, 6}};
	odVec3		points[5];
	odBounds	bounds(M_INFINITY, -M_INFINITY);
	int			scissor[4];
	float		depth[2];
	int			i;

	if (r_skipScissors->integerValue && r_skipDepthBounds->integerValue){
		drawLight->scissorX = tr.viewParms.viewportX;
		drawLight->scissorY = tr.viewParms.viewportY;
		drawLight->scissorWidth = tr.viewParms.viewportWidth;
		drawLight->scissorHeight = tr.viewParms.viewportHeight;

		drawLight->depthMin = 0.0f;
		drawLight->depthMax = 1.0f;

		return;
	}

	// Copy the corner points of each plane and clip to the frustum
	for (i = 0; i < 6; i++){
		points[0] = drawLight->data.corners[cornerIndices[i][0]];
		points[1] = drawLight->data.corners[cornerIndices[i][1]];
		points[2] = drawLight->data.corners[cornerIndices[i][2]];
		points[3] = drawLight->data.corners[cornerIndices[i][3]];

		R_ClipLightPlane(bounds, 4, points, 0);
	}

	// Check if any corner point is not in front of the near plane
	for (i = 0; i < 8; i++){
		if (tr.viewParms.frustum[4].PointOnSide(drawLight->data.corners[i], ON_EPSILON) != PLANESIDE_FRONT){
			bounds[0][2] = -1.0f;
			break;
		}
	}

	// Transform into screen space
	bounds[0][0] = (0.5f + 0.5f * bounds[0][0]) * tr.viewParms.viewportWidth + tr.viewParms.viewportX;
	bounds[0][1] = (0.5f + 0.5f * bounds[0][1]) * tr.viewParms.viewportHeight + tr.viewParms.viewportY;
	bounds[0][2] = (0.5f + 0.5f * bounds[0][2]);
	bounds[1][0] = (0.5f + 0.5f * bounds[1][0]) * tr.viewParms.viewportWidth + tr.viewParms.viewportX;
	bounds[1][1] = (0.5f + 0.5f * bounds[1][1]) * tr.viewParms.viewportHeight + tr.viewParms.viewportY;
	bounds[1][2] = (0.5f + 0.5f * bounds[1][2]);

	// Fog lights don't need depth bounds testing
	if (drawLight->material->lightType == LT_FOG){
		bounds[0][2] = 0.0f;
		bounds[1][2] = 1.0f;
	}

	// Set the scissor rectangle
	if (r_skipScissors->integerValue){
		drawLight->scissorX = tr.viewParms.viewportX;
		drawLight->scissorY = tr.viewParms.viewportY;
		drawLight->scissorWidth = tr.viewParms.viewportWidth;
		drawLight->scissorHeight = tr.viewParms.viewportHeight;
	}
	else {
		scissor[0] = Max(M_FtolFast(M_Floor(bounds[0][0])), tr.viewParms.viewportX);
		scissor[1] = Max(M_FtolFast(M_Floor(bounds[0][1])), tr.viewParms.viewportY);
		scissor[2] = Min(M_FtolFast(M_Ceil(bounds[1][0])), tr.viewParms.viewportX + tr.viewParms.viewportWidth);
		scissor[3] = Min(M_FtolFast(M_Ceil(bounds[1][1])), tr.viewParms.viewportY + tr.viewParms.viewportHeight);

		if (scissor[0] > scissor[2] || scissor[1] > scissor[3]){
			drawLight->scissorX = tr.viewParms.viewportX;
			drawLight->scissorY = tr.viewParms.viewportY;
			drawLight->scissorWidth = tr.viewParms.viewportWidth;
			drawLight->scissorHeight = tr.viewParms.viewportHeight;
		}
		else {
			drawLight->scissorX = scissor[0];
			drawLight->scissorY = scissor[1];
			drawLight->scissorWidth = scissor[2] - scissor[0];
			drawLight->scissorHeight = scissor[3] - scissor[1];
		}
	}

	// Set the depth bounds
	if (r_skipDepthBounds->integerValue){
		drawLight->depthMin = 0.0f;
		drawLight->depthMax = 1.0f;
	}
	else {
		depth[0] = Max(bounds[0][2], 0.0f);
		depth[1] = Min(bounds[1][2], 1.0f);

		if (depth[0] > depth[1]){
			drawLight->depthMin = 0.0f;
			drawLight->depthMax = 1.0f;
		}
		else {
			drawLight->depthMin = depth[0];
			drawLight->depthMax = depth[1];
		}
	}
}


/*
 ==============================================================================

 INTERACTION LIST GENERATION

 ==============================================================================
*/


/*
 ==================
 R_AddInteractionDrawMesh
 ==================
*/
static void R_AddInteractionDrawMesh (drawLight_t *drawLight, meshType_t type, mesh_t *mesh, material_t *material, entity_t *entity){

	drawMesh_t	*drawMesh;

	tr.pc.meshesInteraction++;

	if ((drawLight->material->lightType == LT_FOG || drawLight->material->lightType == LT_BLEND) || !(material->flags & MF_NOSELFSHADOW)){
		if (drawLight->numInteractionMeshes[0] == MAX_DRAW_MESHES){
			Com_DPrintf(S_COLOR_YELLOW "R_AddInteractionDrawMesh: MAX_DRAW_MESHES hit\n");
			return;
		}

		drawMesh = &r_interactionMeshes[0][drawLight->numInteractionMeshes[0]++];
	}
	else {
		if (drawLight->numInteractionMeshes[1] == MAX_DRAW_MESHES){
			Com_DPrintf(S_COLOR_YELLOW "R_AddInteractionDrawMesh: MAX_DRAW_MESHES hit\n");
			return;
		}

		drawMesh = &r_interactionMeshes[1][drawLight->numInteractionMeshes[1]++];
	}

	drawMesh->sort = (material->index << SORT_SHIFT_MATERIAL) | (entity->index << SORT_SHIFT_ENTITY) | (type << SORT_SHIFT_TYPE);
	drawMesh->mesh = mesh;
}

/*
 ==================
 R_AddFoliageSurfaceInteraction
 ==================
*/
static void R_AddFoliageSurfaceInteraction (drawLight_t *drawLight, surface_t *surface, material_t *material, entity_t *entity, int cullBits){

	foliageInstance_t	*foliageInstance;
	int					i;

	if (r_skipFoliage->integerValue)
		return;

	// Cull bounds
	if (cullBits){
		if (entity == tr.scene->worldEntity)
			cullBits = R_LightCullBounds(&drawLight->data, surface->bounds, cullBits);
		else
			cullBits = R_LightCullEntityBounds(&drawLight->data, surface->bounds, cullBits, entity);

		if (cullBits == CULL_OUT)
			return;
	}

	// If it has a single foliage instance, no need to cull again
	if (surface->numFoliageInstances == 1)
		cullBits = 0;

	// Add all the foliage instances
	for (i = 0, foliageInstance = surface->foliageInstances; i < surface->numFoliageInstances; i++, foliageInstance++){
		if (foliageInstance->viewCount != tr.viewCount)
			continue;		// Not visible

		// Cull sphere
		if (cullBits){
			if (entity == tr.scene->worldEntity){
				if (R_LightCullSphere(&drawLight->data, foliageInstance->origin, surface->foliageRadius, cullBits) == CULL_OUT)
					continue;
			}
			else {
				if (R_LightCullEntitySphere(&drawLight->data, foliageInstance->origin, surface->foliageRadius, cullBits, entity) == CULL_OUT)
					continue;
			}
		}

		if (drawLight->material->lightType == LT_GENERIC || drawLight->material->lightType == LT_AMBIENT)
			tr.pc.interactionsDLight++;
		else
			tr.pc.interactionsDFog++;

		// Add the draw mesh
		R_AddInteractionDrawMesh(drawLight, MESH_FOLIAGE, foliageInstance, material, entity);
	}
}

/*
 ==================
 R_AddSurfaceInteraction
 ==================
*/
static void R_AddSurfaceInteraction (drawLight_t *drawLight, surface_t *surface, material_t *material, entity_t *entity, const odVec3 &lightOrigin, int cullBits){

	int		side;

	if (surface->type == ST_FOLIAGE){
		R_AddFoliageSurfaceInteraction(drawLight, surface, material, entity, cullBits);
		return;
	}

	// Cull face
	if (drawLight->material->lightType == LT_GENERIC){
		if (surface->plane && material->cullType != CT_TWO_SIDED){
			side = surface->plane->PointOnSide(lightOrigin);

			if (material->cullType == CT_FRONT_SIDED){
				if (side != PLANESIDE_FRONT)
					return;
			}
			else {
				if (side != PLANESIDE_BACK)
					return;
			}
		}
	}

	// Cull bounds
	if (cullBits){
		if (entity == tr.scene->worldEntity)
			cullBits = R_LightCullBounds(&drawLight->data, surface->bounds, cullBits);
		else
			cullBits = R_LightCullEntityBounds(&drawLight->data, surface->bounds, cullBits, entity);

		if (cullBits == CULL_OUT)
			return;
	}

	if (drawLight->material->lightType == LT_GENERIC || drawLight->material->lightType == LT_AMBIENT)
		tr.pc.interactionsDLight++;
	else
		tr.pc.interactionsDFog++;

	// Add the draw mesh
	R_AddInteractionDrawMesh(drawLight, MESH_SURFACE, surface, material, entity);
}

/*
 ==================
 R_RecursiveWorldInteractionsNode
 ==================
*/
static void R_RecursiveWorldInteractionsNode (drawLight_t *drawLight, node_t *node, int cullBits){

	surface_t	*surface;
	material_t	*material;
	int			i;

	if (node->viewCount != tr.viewCount)
		return;		// Not visible

	// Cull bounds
	if (cullBits){
		cullBits = R_LightCullBounds(&drawLight->data, node->bounds, cullBits);

		if (cullBits == CULL_OUT)
			return;
	}

	// If a node, recurse down the children
	if (!node->isLeaf){
		R_RecursiveWorldInteractionsNode(drawLight, node->children[0], cullBits);
		R_RecursiveWorldInteractionsNode(drawLight, node->children[1], cullBits);
		return;
	}

	// Leaf node
	if (!node->numLeafSurfaces)
		return;

	// Check if the leaf is in the light PVS
	if (!r_skipVisibility->integerValue){
		if (drawLight->material->lightType == LT_GENERIC){
			if (drawLight->data.pvs && !(drawLight->data.pvs[node->cluster >> 3] & BIT(node->cluster & 7)))
				return;
		}
	}

	// If it has a single surface, no need to cull again
	if (node->numLeafSurfaces == 1)
		cullBits = 0;

	// Add all the surfaces
	for (i = 0; i < node->numLeafSurfaces; i++){
		surface = node->leafSurfaces[i];

		if (surface->lightCount == tr.lightCount)
			continue;		// Already added this surface from another leaf
		surface->lightCount = tr.lightCount;

		if (surface->viewCount != tr.viewCount)
			continue;		// Not visible

		// Get the material
		material = surface->material;

		if (material->deform != DFRM_NONE)
			continue;		// Dynamically deformed surface

		if (drawLight->material->lightType == LT_GENERIC || drawLight->material->lightType == LT_AMBIENT){
			if (material->numStages == material->numAmbientStages)
				continue;		// Don't bother drawing
		}
		else {
			if (material->flags & MF_NOFOG)
				continue;		// Don't bother drawing
		}

		if (material->spectrum > drawLight->material->spectrum)
			continue;		// Not illuminated by this light

		// Add the surface
		R_AddSurfaceInteraction(drawLight, surface, material, tr.scene->worldEntity, drawLight->data.origin, cullBits);
	}
}

/*
 ==================
 R_AddWorldInteractions
 ==================
*/
static void R_AddWorldInteractions (drawLight_t *drawLight){

	lightNode_t			*lightNode;
	surface_t			*surface;
	foliageInstance_t	*foliageInstance;
	int					i, j;

	if (!tr.viewParms.primaryView)
		return;

	// Bump light count
	tr.lightCount++;

	// If we have a precompiled list of interactions
	if (!r_skipPrecompiledInteractions->integerValue && drawLight->data.precompiled){
		// Check all the leaf nodes
		for (lightNode = drawLight->data.interactionNodes; lightNode; lightNode = lightNode->next){
			if (lightNode->leaf->viewCount != tr.viewCount)
				continue;		// Not visible

			// Add all the surfaces
			for (i = 0; i < lightNode->numLeafSurfaces; i++){
				surface = lightNode->leafSurfaces[i];

				if (surface->lightCount == tr.lightCount)
					continue;		// Already added this surface from another leaf
				surface->lightCount = tr.lightCount;

				if (surface->viewCount != tr.viewCount)
					continue;		// Not visible

				if (surface->type == ST_FOLIAGE){
					if (r_skipFoliage->integerValue)
						continue;

					// Add all the foliage instances
					for (j = 0, foliageInstance = surface->foliageInstances; j < surface->numFoliageInstances; j++, foliageInstance++){
						if (foliageInstance->viewCount != tr.viewCount)
							continue;		// Not visible

						// Cull sphere
						if (R_LightCullSphere(&drawLight->data, foliageInstance->origin, surface->foliageRadius, 63) == CULL_OUT)
							continue;

						if (drawLight->material->lightType == LT_GENERIC || drawLight->material->lightType == LT_AMBIENT)
							tr.pc.interactionsSLight++;
						else
							tr.pc.interactionsSFog++;

						// Add the draw mesh
						R_AddInteractionDrawMesh(drawLight, MESH_FOLIAGE, foliageInstance, surface->material, tr.scene->worldEntity);
					}

					continue;
				}

				if (drawLight->material->lightType == LT_GENERIC || drawLight->material->lightType == LT_AMBIENT)
					tr.pc.interactionsSLight++;
				else
					tr.pc.interactionsSFog++;

				// Add the draw mesh
				R_AddInteractionDrawMesh(drawLight, MESH_SURFACE, surface, surface->material, tr.scene->worldEntity);
			}
		}

		return;
	}

	// Walk the BSP tree
	if (!r_skipInteractionCulling->integerValue)
		R_RecursiveWorldInteractionsNode(drawLight, tr.world->nodes, 63);
	else
		R_RecursiveWorldInteractionsNode(drawLight, tr.world->nodes, 0);
}

/*
 ==================
 R_AddInlineModelInteractions
 ==================
*/
static void R_AddInlineModelInteractions (drawLight_t *drawLight, entity_t *entity){

	inlineModel_t	*model = (inlineModel_t *)entity->e.model->data;
	surface_t		*surface;
	material_t		*material;
	odVec3			lightOrigin;
	int				cullBits;
	int				i;

	// Cull bounds
	if (!r_skipInteractionCulling->integerValue && !entity->e.depthHack){
		cullBits = R_LightCullEntityBounds(&drawLight->data, model->bounds, 63, entity);

		if (cullBits == CULL_OUT)
			return;
	}
	else
		cullBits = 0;

	tr.pc.entitiesInteraction++;

	// Perform a callback if needed
	if (entity->e.callback){
		entity->e.callback(&entity->e);

		entity->e.callback = NULL;
	}

	// Transform light origin into local space
	entity->e.axis.ProjectVector(drawLight->data.origin - entity->e.origin, lightOrigin);

	// If it has a single surface, no need to cull again
	if (model->numSurfaces == 1)
		cullBits = 0;

	// Add all the surfaces
	for (i = 0, surface = model->surfaces; i < model->numSurfaces; i++, surface++){
		// Get the material
		if (entity->e.material)
			material = entity->e.material;
		else
			material = surface->material;

		if (material->deform != DFRM_NONE)
			continue;		// Dynamically deformed surface

		if (drawLight->material->lightType == LT_GENERIC || drawLight->material->lightType == LT_AMBIENT){
			if (material->numStages == material->numAmbientStages)
				continue;		// Don't bother drawing
		}
		else {
			if (material->flags & MF_NOFOG)
				continue;		// Don't bother drawing
		}

		if (material->spectrum > drawLight->material->spectrum)
			continue;		// Not illuminated by this light

		// Add the surface
		R_AddSurfaceInteraction(drawLight, surface, material, entity, lightOrigin, cullBits);
	}
}

/*
 ==================
 R_AddMDLModelInteractions
 ==================
*/
static void R_AddMDLModelInteractions (drawLight_t *drawLight, entity_t *entity){

	mdlModel_t		*model = (mdlModel_t *)entity->e.model->data;
	mdlSurface_t	*surface;
	material_t		*material;
	int				cullBits;
	int				i;

	// Cull bounds
	if (!r_skipInteractionCulling->integerValue && !entity->e.depthHack){
		cullBits = R_LightCullEntityBounds(&drawLight->data, model->bounds, 63, entity);

		if (cullBits == CULL_OUT)
			return;
	}
	else
		cullBits = 0;

	tr.pc.entitiesInteraction++;

	// Perform a callback if needed
	if (entity->e.callback){
		entity->e.callback(&entity->e);

		entity->e.callback = NULL;
	}

	// If it has a single surface, no need to cull again
	if (model->numSurfaces == 1)
		cullBits = 0;

	// Add all the surfaces
	for (i = 0, surface = model->surfaces; i < model->numSurfaces; i++, surface++){
		// Get the material
		if (entity->e.material)
			material = entity->e.material;
		else
			material = surface->material;

		if (material->deform != DFRM_NONE)
			continue;		// Dynamically deformed surface

		if (drawLight->material->lightType == LT_GENERIC || drawLight->material->lightType == LT_AMBIENT){
			if (material->numStages == material->numAmbientStages)
				continue;		// Don't bother drawing
		}
		else {
			if (material->flags & MF_NOFOG)
				continue;		// Don't bother drawing
		}

		if (material->spectrum > drawLight->material->spectrum)
			continue;		// Not illuminated by this light

		// Cull bounds
		if (cullBits){
			if (R_LightCullEntityBounds(&drawLight->data, surface->bounds, cullBits, entity) == CULL_OUT)
				continue;
		}

		if (drawLight->material->lightType == LT_GENERIC || drawLight->material->lightType == LT_AMBIENT)
			tr.pc.interactionsDLight++;
		else
			tr.pc.interactionsDFog++;

		// Add the draw mesh
		R_AddInteractionDrawMesh(drawLight, MESH_MODEL, surface, material, entity);
	}
}

/*
static void R_AddMD5ModelInteractions (drawLight_t *drawLight, entity_t *entity){

	mdlModel_t		*model;
	mdlSurface_t	*surface;
	material_t		*material;
	int				cullBits;
	int				i;

	// Cull bounds
	if (!r_skipInteractionCulling->integerValue && !entity->e.depthHack){
		cullBits = R_LightCullEntityBounds(&drawLight->data, entity->e.bounds, 63, entity);

		if (cullBits == CULL_OUT)
			return;
	}
	else
		cullBits = 0;

	tr.pc.entitiesInteraction++;

	// Perform a callback if needed
	if (entity->e.callback){
		entity->e.callback(&entity->e);

		entity->e.callback = NULL;
	}

	// Instantiate
	model = R_InstantiateDynamicModel(entity, true, false);

	// If it has a single surface, no need to cull again
	if (model->numSurfaces == 1)
		cullBits = 0;

	// Add all the surfaces
	for (i = 0, surface = model->surfaces; i < model->numSurfaces; i++, surface++){
		// Get the material
		if (entity->e.material)
			material = entity->e.material;
		else
			material = surface->material;

		if (material->deform != DFRM_NONE)
			continue;		// Dynamically deformed surface

		if (drawLight->material->lightType == LT_GENERIC || drawLight->material->lightType == LT_AMBIENT){
			if (material->numStages == material->numAmbientStages)
				continue;		// Don't bother drawing
		}
		else {
			if (material->flags & MF_NOFOG)
				continue;		// Don't bother drawing
		}

		if (material->spectrum > drawLight->material->spectrum)
			continue;		// Not illuminated by this light

		// Cull bounds
		if (cullBits){
			if (R_LightCullEntityBounds(&drawLight->data, surface->bounds, cullBits, entity) == CULL_OUT)
				continue;
		}

		if (drawLight->material->lightType == LT_GENERIC || drawLight->material->lightType == LT_AMBIENT)
			tr.pc.interactionsDLight++;
		else
			tr.pc.interactionsDFog++;

		// Add the draw mesh
		R_AddInteractionDrawMesh(drawLight, MESH_MODEL, surface, material, entity);
	}
}
*/
/*
 ==================
 R_AddEntityInteractions
 ==================
*/
static void R_AddEntityInteractions (drawLight_t *drawLight){

	entity_t	*entity;
	model_t		*model;

	if (r_skipEntities->integerValue)
		return;

	for (entity = tr.scene->activeEntity.next; entity != &tr.scene->activeEntity; entity = entity->next){
		if (entity == tr.scene->worldEntity)
			continue;

		if (entity->viewCount != tr.viewCount)
			continue;		// Not visible

		if (entity->e.type != RE_MODEL)
			continue;		// Not a model

		// Development tool
		if (r_singleEntity->integerValue >= 0){
			if (r_singleEntity->integerValue != entity->index)
				continue;
		}

		// Check for view suppression
		if (!r_skipSuppress->integerValue){
			if (!(entity->e.allowInView & tr.viewParms.viewType))
				continue;
		}

		// Add the entity
		model = entity->e.model;

		if (!model || model->type == MODEL_BAD)
			continue;

		switch (model->type){
		case MODEL_INLINE:
			R_AddInlineModelInteractions(drawLight, entity);
			break;
		case MODEL_MDL:
			R_AddMDLModelInteractions(drawLight, entity);
			break;
		//case MODEL_MD5:
		//	R_AddMD5ModelInteractions(drawLight, entity);
		//	break;
		default:
			Com_Error(false, "R_AddEntityInteractions: bad model type (%i)", model->type);
		}
	}
}

/*
 ==================
 R_GenerateInteractionsList
 ==================
*/
static void R_GenerateInteractionsList (drawLight_t *drawLight){

	// Clear
	drawLight->numInteractionMeshes[0] = 0;
	drawLight->numInteractionMeshes[1] = 0;

	drawLight->interactionMeshes[0] = NULL;
	drawLight->interactionMeshes[1] = NULL;

	// Add draw meshes
	R_AddWorldInteractions(drawLight);
	R_AddEntityInteractions(drawLight);

	// Generate the lists
	if (drawLight->numInteractionMeshes[0]){
		drawLight->interactionMeshes[0] = (drawMesh_t *)Mem_Alloc(drawLight->numInteractionMeshes[0] * sizeof(drawMesh_t), TAG_RENDERER);
		memcpy(drawLight->interactionMeshes[0], r_interactionMeshes[0], drawLight->numInteractionMeshes[0] * sizeof(drawMesh_t));
	}
	if (drawLight->numInteractionMeshes[1]){
		drawLight->interactionMeshes[1] = (drawMesh_t *)Mem_Alloc(drawLight->numInteractionMeshes[1] * sizeof(drawMesh_t), TAG_RENDERER);
		memcpy(drawLight->interactionMeshes[1], r_interactionMeshes[1], drawLight->numInteractionMeshes[1] * sizeof(drawMesh_t));
	}
}


/*
 ==============================================================================

 SHADOW LIST GENERATION

 ==============================================================================
*/


/*
 ==================
 R_AddShadowDrawMesh
 ==================
*/
static void R_AddShadowDrawMesh (drawLight_t *drawLight, meshType_t type, mesh_t *mesh, material_t *material, entity_t *entity, bool caps){

	drawMesh_t	*drawMesh;

	tr.pc.meshesShadow++;

	if (!(material->flags & MF_NOSELFSHADOW)){
		if (drawLight->numShadowMeshes[0] == MAX_DRAW_MESHES){
			Com_DPrintf(S_COLOR_YELLOW "R_AddShadowDrawMesh: MAX_DRAW_MESHES hit\n");
			return;
		}

		drawMesh = &r_shadowMeshes[0][drawLight->numShadowMeshes[0]++];
	}
	else {
		if (drawLight->numShadowMeshes[1] == MAX_DRAW_MESHES){
			Com_DPrintf(S_COLOR_YELLOW "R_AddShadowDrawMesh: MAX_DRAW_MESHES hit\n");
			return;
		}

		drawMesh = &r_shadowMeshes[1][drawLight->numShadowMeshes[1]++];
	}

	drawMesh->sort = (material->index << SORT_SHIFT_MATERIAL) | (entity->index << SORT_SHIFT_ENTITY) | (type << SORT_SHIFT_TYPE) | (caps);
	drawMesh->mesh = mesh;
}

/*
 ==================
 R_AddSurfaceShadow
 ==================
*/
static void R_AddSurfaceShadow (drawLight_t *drawLight, surface_t *surface, material_t *material, entity_t *entity, const odVec3 &lightOrigin, int cullBits, int cullShadowBits){

	int		side;
	bool	caps;

	// Cull face
	if (surface->plane){
		side = surface->plane->PointOnSide(lightOrigin);

		if (side != PLANESIDE_FRONT)
			return;
	}

	// Cull bounds
	if (cullBits){
		if (entity == tr.scene->worldEntity)
			cullBits = R_LightCullBounds(&drawLight->data, surface->bounds, cullBits);
		else
			cullBits = R_LightCullEntityBounds(&drawLight->data, surface->bounds, cullBits, entity);

		if (cullBits == CULL_OUT)
			return;
	}

	// Cull shadow
	if (cullShadowBits){
		if (entity == tr.scene->worldEntity){
			if (surface->viewCount != tr.viewCount)
				cullShadowBits = R_LightCullShadow(&drawLight->data, surface->bounds, cullShadowBits);
		}
		else {
			if (entity->viewCount != tr.viewCount)
				cullShadowBits = R_LightCullEntityShadow(&drawLight->data, surface->bounds, cullShadowBits, entity);
		}

		if (cullShadowBits == CULL_OUT)
			return;
	}

	// Determine if shadow caps are needed
	if (!r_skipShadowCapsCulling->integerValue){
		if (entity == tr.scene->worldEntity)
			caps = R_ShadowInNearClipVolume(surface->bounds);
		else
			caps = R_EntityShadowInNearClipVolume(surface->bounds, entity);
	}
	else
		caps = true;

	if (caps)
		tr.pc.shadowsDZFail++;
	else
		tr.pc.shadowsDZPass++;

	// Add the draw mesh
	R_AddShadowDrawMesh(drawLight, MESH_SURFACE, surface, material, entity, caps);
}

/*
 ==================
 R_RecursiveWorldShadowsNode
 ==================
*/
static void R_RecursiveWorldShadowsNode (drawLight_t *drawLight, node_t *node, int cullBits, int cullShadowBits){

	surface_t	*surface;
	material_t	*material;
	int			i;

	// Cull bounds
	if (cullBits){
		cullBits = R_LightCullBounds(&drawLight->data, node->bounds, cullBits);

		if (cullBits == CULL_OUT)
			return;
	}

	// Cull shadow
	if (cullShadowBits){
		if (node->viewCount != tr.viewCount){
			cullShadowBits = R_LightCullShadow(&drawLight->data, node->bounds, cullShadowBits);

			if (cullShadowBits == CULL_OUT)
				return;
		}
	}

	// If a node, recurse down the children
	if (!node->isLeaf){
		R_RecursiveWorldShadowsNode(drawLight, node->children[0], cullBits, cullShadowBits);
		R_RecursiveWorldShadowsNode(drawLight, node->children[1], cullBits, cullShadowBits);
		return;
	}

	// Leaf node
	if (!node->numLeafSurfaces)
		return;

	// Check if the leaf is in the light PVS
	if (!r_skipVisibility->integerValue){
		if (drawLight->data.pvs && !(drawLight->data.pvs[node->cluster >> 3] & BIT(node->cluster & 7)))
			return;
	}

	// If it has a single surface, no need to cull again
	if (node->numLeafSurfaces == 1)
		cullBits = cullShadowBits = 0;

	// Add all the surfaces
	for (i = 0; i < node->numLeafSurfaces; i++){
		surface = node->leafSurfaces[i];

		if (surface->lightCount == tr.lightCount)
			continue;		// Already added this surface from another leaf
		surface->lightCount = tr.lightCount;

		if (surface->type == ST_FOLIAGE)
			continue;		// Not an actual surface

		// Get the material
		material = surface->material;

		if (material->flags & MF_NOSHADOWS)
			continue;		// Don't bother drawing

		if (material->spectrum > drawLight->material->spectrum)
			continue;		// Not illuminated by this light

		// Add the surface
		R_AddSurfaceShadow(drawLight, surface, material, tr.scene->worldEntity, drawLight->data.origin, cullBits, cullShadowBits);
	}
}

/*
 ==================
 R_AddWorldShadows
 ==================
*/
static void R_AddWorldShadows (drawLight_t *drawLight){

	lightNode_t	*lightNode;
	surface_t	*surface;
	int			cullShadowBits;
	bool		caps;
	int			i;

	if (!tr.viewParms.primaryView)
		return;

	// Bump light count
	tr.lightCount++;

	// If we have a precompiled list of shadows
	if (!r_skipPrecompiledShadows->integerValue && drawLight->data.precompiled){
		// Check all the leaf nodes
		for (lightNode = drawLight->data.shadowNodes; lightNode; lightNode = lightNode->next){
			// Cull shadow
			if (lightNode->leaf->viewCount != tr.viewCount){
				cullShadowBits = R_LightCullShadow(&drawLight->data, lightNode->leaf->bounds, 31);

				if (cullShadowBits == CULL_OUT)
					continue;
			}
			else
				cullShadowBits = 31;

			// If it has a single surface, no need to cull again
			if (lightNode->numLeafSurfaces == 1)
				cullShadowBits = 0;

			// Add all the surfaces
			for (i = 0; i < lightNode->numLeafSurfaces; i++){
				surface = lightNode->leafSurfaces[i];

				if (surface->lightCount == tr.lightCount)
					continue;		// Already added this surface from another leaf
				surface->lightCount = tr.lightCount;

				// Cull shadow
				if (cullShadowBits){
					if (surface->viewCount != tr.viewCount){
						if (R_LightCullShadow(&drawLight->data, surface->bounds, cullShadowBits) == CULL_OUT)
							continue;
					}
				}

				// Determine if shadow caps are needed
				caps = R_ShadowInNearClipVolume(surface->bounds);

				if (caps)
					tr.pc.shadowsSZFail++;
				else
					tr.pc.shadowsSZPass++;

				// Add the draw mesh
				R_AddShadowDrawMesh(drawLight, MESH_SURFACE, surface, surface->material, tr.scene->worldEntity, caps);
			}
		}

		return;
	}

	// Walk the BSP tree
	if (!r_skipShadowCulling->integerValue){
		if (!r_skipShadowProjectionCulling->integerValue)
			R_RecursiveWorldShadowsNode(drawLight, tr.world->nodes, 63, 31);
		else
			R_RecursiveWorldShadowsNode(drawLight, tr.world->nodes, 63, 0);
	}
	else {
		if (!r_skipShadowProjectionCulling->integerValue)
			R_RecursiveWorldShadowsNode(drawLight, tr.world->nodes, 0, 31);
		else
			R_RecursiveWorldShadowsNode(drawLight, tr.world->nodes, 0, 0);
	}
}

/*
 ==================
 R_AddInlineModelShadows
 ==================
*/
static void R_AddInlineModelShadows (drawLight_t *drawLight, entity_t *entity){

	inlineModel_t	*model = (inlineModel_t *)entity->e.model->data;
	surface_t		*surface;
	material_t		*material;
	odVec3			lightOrigin;
	int				cullBits, cullShadowBits;
	int				i;

	// Never cast shadows from depth-hacked models
	if (entity->e.depthHack)
		return;

	// Cull bounds
	if (!r_skipShadowCulling->integerValue){
		cullBits = R_LightCullEntityBounds(&drawLight->data, model->bounds, 63, entity);

		if (cullBits == CULL_OUT)
			return;
	}
	else
		cullBits = 0;

	// Cull shadow
	if (!r_skipShadowProjectionCulling->integerValue){
		if (entity->viewCount != tr.viewCount){
			cullShadowBits = R_LightCullEntityShadow(&drawLight->data, model->bounds, 31, entity);

			if (cullShadowBits == CULL_OUT)
				return;
		}
		else
			cullShadowBits = 0;
	}
	else
		cullShadowBits = 0;

	tr.pc.entitiesShadow++;

	// Perform a callback if needed
	if (entity->e.callback){
		entity->e.callback(&entity->e);

		entity->e.callback = NULL;
	}

	// Transform light origin into local space
	entity->e.axis.ProjectVector(drawLight->data.origin - entity->e.origin, lightOrigin);

	// If it has a single surface, no need to cull again
	if (model->numSurfaces == 1)
		cullBits = cullShadowBits = 0;

	// Add all the surfaces
	for (i = 0, surface = model->surfaces; i < model->numSurfaces; i++, surface++){
		if (surface->type == ST_FOLIAGE)
			continue;		// Not an actual surface

		// Get the material
		if (entity->e.material)
			material = entity->e.material;
		else
			material = surface->material;

		if (material->flags & MF_NOSHADOWS)
			continue;		// Don't bother drawing

		if (material->spectrum > drawLight->material->spectrum)
			continue;		// Not illuminated by this light

		// Add the surface
		R_AddSurfaceShadow(drawLight, surface, material, entity, lightOrigin, cullBits, cullShadowBits);
	}
}

/*
 ==================
 R_AddMDLModelShadows
 ==================
*/
static void R_AddMDLModelShadows (drawLight_t *drawLight, entity_t *entity){

	mdlModel_t		*model = (mdlModel_t *)entity->e.model->data;
	mdlSurface_t	*surface;
	material_t		*material;
	int				cullBits, cullShadowBits;
	bool			caps;
	int				i;

	// Never cast shadows from depth-hacked models
	if (entity->e.depthHack)
		return;

	// Cull bounds
	if (!r_skipShadowCulling->integerValue){
		cullBits = R_LightCullEntityBounds(&drawLight->data, model->bounds, 63, entity);

		if (cullBits == CULL_OUT)
			return;
	}
	else
		cullBits = 0;

	// Cull shadow
	if (!r_skipShadowProjectionCulling->integerValue){
		if (entity->viewCount != tr.viewCount){
			cullShadowBits = R_LightCullEntityShadow(&drawLight->data, model->bounds, 31, entity);

			if (cullShadowBits == CULL_OUT)
				return;
		}
		else
			cullShadowBits = 0;
	}
	else
		cullShadowBits = 0;

	tr.pc.entitiesShadow++;

	// Perform a callback if needed
	if (entity->e.callback){
		entity->e.callback(&entity->e);

		entity->e.callback = NULL;
	}

	// If it has a single surface, no need to cull again
	if (model->numSurfaces == 1)
		cullBits = cullShadowBits = 0;

	// Add all the surfaces
	for (i = 0, surface = model->surfaces; i < model->numSurfaces; i++, surface++){
		// Get the material
		if (entity->e.material)
			material = entity->e.material;
		else
			material = surface->material;

		if (material->flags & MF_NOSHADOWS)
			continue;		// Don't bother drawing

		if (material->spectrum > drawLight->material->spectrum)
			continue;		// Not illuminated by this light

		// Cull bounds
		if (cullBits){
			if (R_LightCullEntityBounds(&drawLight->data, surface->bounds, cullBits, entity) == CULL_OUT)
				continue;
		}

		// Cull shadow
		if (cullShadowBits){
			if (R_LightCullEntityShadow(&drawLight->data, surface->bounds, cullShadowBits, entity) == CULL_OUT)
				continue;
		}

		// Determine if shadow caps are needed
		if (!r_skipShadowCapsCulling->integerValue)
			caps = R_EntityShadowInNearClipVolume(surface->bounds, entity);
		else
			caps = true;

		if (caps)
			tr.pc.shadowsDZFail++;
		else
			tr.pc.shadowsDZPass++;

		// Add the draw mesh
		R_AddShadowDrawMesh(drawLight, MESH_MODEL, surface, material, entity, caps);
	}
}

/*
static void R_AddMD5ModelShadows (drawLight_t *drawLight, entity_t *entity){

	mdlModel_t		*model;
	mdlSurface_t	*surface;
	material_t		*material;
	int				cullBits, cullShadowBits;
	bool			caps;
	int				i;

	// Never cast shadows from depth-hacked models
	if (entity->e.depthHack)
		return;

	// Cull bounds
	if (!r_skipShadowCulling->integerValue){
		cullBits = R_LightCullEntityBounds(&drawLight->data, entity->e.bounds, 63, entity);

		if (cullBits == CULL_OUT)
			return;
	}
	else
		cullBits = 0;

	// Cull shadow
	if (!r_skipShadowProjectionCulling->integerValue){
		if (entity->viewCount != tr.viewCount){
			cullShadowBits = R_LightCullEntityShadow(&drawLight->data, entity->e.bounds, 31, entity);

			if (cullShadowBits == CULL_OUT)
				return;
		}
		else
			cullShadowBits = 0;
	}
	else
		cullShadowBits = 0;

	tr.pc.entitiesShadow++;

	// Perform a callback if needed
	if (entity->e.callback){
		entity->e.callback(&entity->e);

		entity->e.callback = NULL;
	}

	// Instantiate
	model = R_InstantiateDynamicModel(entity, false, true);

	// If it has a single surface, no need to cull again
	if (model->numSurfaces == 1)
		cullBits = cullShadowBits = 0;

	// Add all the surfaces
	for (i = 0, surface = model->surfaces; i < model->numSurfaces; i++, surface++){
		// Get the material
		if (entity->e.material)
			material = entity->e.material;
		else
			material = surface->material;

		if (material->flags & MF_NOSHADOWS)
			continue;		// Don't bother drawing

		if (material->spectrum > drawLight->material->spectrum)
			continue;		// Not illuminated by this light

		// Cull bounds
		if (cullBits){
			if (R_LightCullEntityBounds(&drawLight->data, surface->bounds, cullBits, entity) == CULL_OUT)
				continue;
		}

		// Cull shadows
		if (cullShadowBits){
			if (R_LightCullEntityShadow(&drawLight->data, surface->bounds, cullShadowBits, entity) == CULL_OUT)
				continue;
		}

		// Determine if shadow caps are needed
		if (!r_skipShadowCapsCulling->integerValue)
			caps = R_EntityShadowInNearClipVolume(surface->bounds, entity);
		else
			caps = true;

		if (caps)
			tr.pc.shadowsDZFail++;
		else
			tr.pc.shadowsDZPass++;

		// Add the draw mesh
		R_AddShadowDrawMesh(drawLight, MESH_MODEL, surface, material, entity, caps);
	}
}
*/
/*
 ==================
 R_AddEntityShadows
 ==================
*/
static void R_AddEntityShadows (drawLight_t *drawLight){

	entity_t	*entity;
	model_t		*model;

	if (r_skipEntities->integerValue)
		return;

	for (entity = tr.scene->activeEntity.next; entity != &tr.scene->activeEntity; entity = entity->next){
		if (entity == tr.scene->worldEntity)
			continue;

		if (entity->e.type != RE_MODEL)
			continue;		// Not a model

		// Development tool
		if (r_singleEntity->integerValue >= 0){
			if (r_singleEntity->integerValue != entity->index)
				continue;
		}

		// Check for view suppression
		if (!r_skipSuppress->integerValue){
			if (!(entity->e.allowShadowInView & tr.viewParms.viewType))
				continue;
		}

		// Add the entity
		model = entity->e.model;

		if (!model || model->type == MODEL_BAD)
			continue;

		switch (model->type){
		case MODEL_INLINE:
			R_AddInlineModelShadows(drawLight, entity);
			break;
		case MODEL_MDL:
			R_AddMDLModelShadows(drawLight, entity);
			break;
		//case MODEL_MD5:
		//	R_AddMD5ModelShadows(drawLight, entity);
		//	break;
		default:
			Com_Error(false, "R_AddEntityShadows: bad model type (%i)", model->type);
		}
	}
}

/*
 ==================
 R_GenerateShadowsList
 ==================
*/
static void R_GenerateShadowsList (drawLight_t *drawLight, bool noShadows){

	// Clear
	drawLight->numShadowMeshes[0] = 0;
	drawLight->numShadowMeshes[1] = 0;

	drawLight->shadowMeshes[0] = NULL;
	drawLight->shadowMeshes[1] = NULL;

	// If it doesn't cast shadows, return immediately
	if (noShadows || (drawLight->material->flags & MF_NOSHADOWS)){
		drawLight->castShadows = false;
		return;
	}

	// Set up near clip volume
	R_SetupNearClipVolume(drawLight->data.origin);

	// Add draw meshes
	R_AddWorldShadows(drawLight);
	R_AddEntityShadows(drawLight);

	// Generate the lists
	if (drawLight->numShadowMeshes[0]){
		drawLight->shadowMeshes[0] = (drawMesh_t *)Mem_Alloc(drawLight->numShadowMeshes[0] * sizeof(drawMesh_t), TAG_RENDERER);
		memcpy(drawLight->shadowMeshes[0], r_shadowMeshes[0], drawLight->numShadowMeshes[0] * sizeof(drawMesh_t));
	}
	if (drawLight->numShadowMeshes[1]){
		drawLight->shadowMeshes[1] = (drawMesh_t *)Mem_Alloc(drawLight->numShadowMeshes[1] * sizeof(drawMesh_t), TAG_RENDERER);
		memcpy(drawLight->shadowMeshes[1], r_shadowMeshes[1], drawLight->numShadowMeshes[1] * sizeof(drawMesh_t));
	}

	// Does it cast shadows?
	drawLight->castShadows = (drawLight->numShadowMeshes[0] + drawLight->numShadowMeshes[1]);
}


/*
 ==============================================================================

 LIGHT COMPILING

 ==============================================================================
*/


/*
 ==================
 R_PrecompileWorldInteractions
 ==================
*/
static void R_PrecompileWorldInteractions (light_t *light, material_t *lightMaterial, node_t *node, int cullBits, surface_t **surfaceList){

	lightNode_t	*lightNode;
	surface_t	*surface;
	material_t	*material;
	int			side;
	int			i, count = 0;

	// Cull bounds
	if (cullBits){
		cullBits = R_LightCullBounds(&light->data, node->bounds, cullBits);

		if (cullBits == CULL_OUT)
			return;
	}

	// If a node, recurse down the children
	if (!node->isLeaf){
		R_PrecompileWorldInteractions(light, lightMaterial, node->children[0], cullBits, surfaceList);
		R_PrecompileWorldInteractions(light, lightMaterial, node->children[1], cullBits, surfaceList);
		return;
	}

	// Leaf node
	if (!node->numLeafSurfaces)
		return;

	// Check if the leaf is in the light PVS
	if (lightMaterial->lightType == LT_GENERIC){
		if (light->data.pvs && !(light->data.pvs[node->cluster >> 3] & BIT(node->cluster & 7)))
			return;
	}

	// If it has a single surface, no need to cull again
	if (node->numLeafSurfaces == 1)
		cullBits = 0;

	// Add all the surfaces
	for (i = 0; i < node->numLeafSurfaces; i++){
		surface = node->leafSurfaces[i];

		// Get the material
		material = surface->material;

		if (material->deform != DFRM_NONE)
			continue;		// Dynamically deformed surface

		if (lightMaterial->lightType == LT_GENERIC || lightMaterial->lightType == LT_AMBIENT){
			if (material->numStages == material->numAmbientStages)
				continue;		// Don't bother drawing
		}
		else {
			if (material->flags & MF_NOFOG)
				continue;		// Don't bother drawing
		}

		if (material->spectrum > lightMaterial->spectrum)
			continue;		// Not illuminated by this light

		// Cull face
		if (lightMaterial->lightType == LT_GENERIC){
			if (surface->plane && material->cullType != CT_TWO_SIDED){
				side = surface->plane->PointOnSide(light->data.origin);

				if (material->cullType == CT_FRONT_SIDED){
					if (side != PLANESIDE_FRONT)
						continue;
				}
				else {
					if (side != PLANESIDE_BACK)
						continue;
				}
			}
		}

		// Cull bounds
		if (cullBits){
			if (R_LightCullBounds(&light->data, surface->bounds, cullBits) == CULL_OUT)
				continue;
		}

		// Add the surface to the temporary list
		if (count == BSP_MAX_SURFACES)
			break;

		surfaceList[count++] = surface;
	}

	// Add a new leaf node
	if (!count)
		return;

	lightNode = (lightNode_t *)Mem_Alloc(sizeof(lightNode_t), TAG_RENDERER);

	lightNode->leaf = node;
	lightNode->numLeafSurfaces = count;
	lightNode->leafSurfaces = (surface_t **)Mem_Alloc(count * sizeof(surface_t *), TAG_RENDERER);

	memcpy(lightNode->leafSurfaces, surfaceList, count * sizeof(surface_t *));

	// Link
	lightNode->next = light->data.interactionNodes;
	light->data.interactionNodes = lightNode;
}

/*
 ==================
 R_PrecompileWorldShadows
 ==================
*/
static void R_PrecompileWorldShadows (light_t *light, material_t *lightMaterial, node_t *node, int cullBits, surface_t **surfaceList){

	lightNode_t	*lightNode;
	surface_t	*surface;
	material_t	*material;
	int			side;
	int			i, count = 0;

	// If it doesn't cast shadows, return immediately
	if (light->l.noShadows || (lightMaterial->flags & MF_NOSHADOWS))
		return;

	// Cull bounds
	if (cullBits){
		cullBits = R_LightCullBounds(&light->data, node->bounds, cullBits);

		if (cullBits == CULL_OUT)
			return;
	}

	// If a node, recurse down the children
	if (!node->isLeaf){
		R_PrecompileWorldShadows(light, lightMaterial, node->children[0], cullBits, surfaceList);
		R_PrecompileWorldShadows(light, lightMaterial, node->children[1], cullBits, surfaceList);
		return;
	}

	// Leaf node
	if (!node->numLeafSurfaces)
		return;

	// Check if the leaf is in the light PVS
	if (light->data.pvs && !(light->data.pvs[node->cluster >> 3] & BIT(node->cluster & 7)))
		return;

	// If it has a single surface, no need to cull again
	if (node->numLeafSurfaces == 1)
		cullBits = 0;

	// Add all the surfaces
	for (i = 0; i < node->numLeafSurfaces; i++){
		surface = node->leafSurfaces[i];

		if (surface->type == ST_FOLIAGE)
			continue;		// Not an actual surface

		// Get the material
		material = surface->material;

		if (material->flags & MF_NOSHADOWS)
			continue;		// Don't bother drawing

		if (material->spectrum > lightMaterial->spectrum)
			continue;		// Not illuminated by this light

		// Cull face
		if (surface->plane){
			side = surface->plane->PointOnSide(light->data.origin);

			if (side != PLANESIDE_FRONT)
				continue;
		}

		// Cull bounds
		if (cullBits){
			if (R_LightCullBounds(&light->data, surface->bounds, cullBits) == CULL_OUT)
				continue;
		}

		// Add the surface to the temporary list
		if (count == BSP_MAX_SURFACES)
			break;

		surfaceList[count++] = surface;
	}

	// Add a new leaf node
	if (!count)
		return;

	lightNode = (lightNode_t *)Mem_Alloc(sizeof(lightNode_t), TAG_RENDERER);

	lightNode->leaf = node;
	lightNode->numLeafSurfaces = count;
	lightNode->leafSurfaces = (surface_t **)Mem_Alloc(count * sizeof(surface_t *), TAG_RENDERER);

	memcpy(lightNode->leafSurfaces, surfaceList, count * sizeof(surface_t *));

	// Link
	lightNode->next = light->data.shadowNodes;
	light->data.shadowNodes = lightNode;
}

/*
 ==================
 R_CompileLights
 ==================
*/
void R_CompileLights (scene_t *scene){

	light_t			*light;
	material_t		*lightMaterial;
	surface_t		*surfaceList[BSP_MAX_SURFACES];
	compiledLight_t	*compiledLight;
	lightNode_t		*lightNode;
	int				totalInteractions = 0, totalInteractionRefs = 0, totalInteractionBytes = 0;
	int				totalShadows = 0, totalShadowRefs = 0, totalShadowBytes = 0;
	int				totalLights = 0;
	int				i, time;

	if (scene->inUse)
		Com_Error(false, "R_CompileLights: scene is currently in use");

	if (!tr.world)
		Com_Error(false, "R_CompileLights: NULL world");

	if (scene->compiledLights)
		return;		// Already compiled

	time = Sys_Milliseconds();

	for (light = scene->activeLight.next; light != &scene->activeLight; light = light->next){
		if (light->l.lightNum < 0 || light->l.lightNum >= MAX_ENTITIES)
			continue;		// Should never happen

		if (scene->compiledLightsList[light->l.lightNum])
			continue;		// Should never happen

		// Get the material
		if (light->l.material)
			lightMaterial = light->l.material;
		else {
			if (light->l.type == RL_POINT)
				lightMaterial = tr.defaultPointLightMaterial;
			else
				lightMaterial = tr.defaultProjectedLightMaterial;
		}

		// Set up the light data
		R_SetupLightData(scene, light, lightMaterial, true);

		// Precompile interactions and shadows
		light->data.precompiled = true;

		R_PrecompileWorldInteractions(light, lightMaterial, tr.world->nodes, 63, surfaceList);
		R_PrecompileWorldShadows(light, lightMaterial, tr.world->nodes, 63, surfaceList);

		// Store the compiled light
		scene->compiledLightsList[light->l.lightNum] = compiledLight = (compiledLight_t *)Mem_Alloc(sizeof(compiledLight_t), TAG_RENDERER);

		compiledLight->l = light->l;
		compiledLight->data = light->data;

		// Update statistics
		tr.lightCount++;

		for (lightNode = compiledLight->data.interactionNodes; lightNode; lightNode = lightNode->next){
			for (i = 0; i < lightNode->numLeafSurfaces; i++){
				if (lightNode->leafSurfaces[i]->lightCount == tr.lightCount)
					continue;
				lightNode->leafSurfaces[i]->lightCount = tr.lightCount;

				totalInteractions++;
			}

			totalInteractionRefs += lightNode->numLeafSurfaces;
			totalInteractionBytes += sizeof(lightNode_t) + (lightNode->numLeafSurfaces * sizeof(surface_t *));
		}

		tr.lightCount++;

		for (lightNode = compiledLight->data.shadowNodes; lightNode; lightNode = lightNode->next){
			for (i = 0; i < lightNode->numLeafSurfaces; i++){
				if (lightNode->leafSurfaces[i]->lightCount == tr.lightCount)
					continue;
				lightNode->leafSurfaces[i]->lightCount = tr.lightCount;

				totalShadows++;
			}

			totalShadowRefs += lightNode->numLeafSurfaces;
			totalShadowBytes += sizeof(lightNode_t) + (lightNode->numLeafSurfaces * sizeof(surface_t *));
		}

		totalLights++;
	}

	scene->compiledLights = true;

	// Print statistics
	Com_Printf("%i lights compiled in %i msec\n", totalLights, Sys_Milliseconds() - time);
	Com_Printf("%i interactions (%i refs) totalling %i KB\n", totalInteractions, totalInteractionRefs, totalInteractionBytes >> 10);
	Com_Printf("%i shadows (%i refs) totalling %i KB\n", totalShadows, totalShadowRefs, totalShadowBytes >> 10);
}


// ============================================================================


/*
 ==================
 R_ShowLightVolume

 Development tool
 ==================
*/
static void R_ShowLightVolume (drawLight_t *drawLight, int number){

	odPlane	*plane;
	bool	inside = true;
	int		i;

	// Check if the view origin is inside the light volume
	for (i = 0, plane = drawLight->data.frustum; i < 6; i++, plane++){
		if (plane->PointOnSide(tr.renderView.origin) == PLANESIDE_BACK){
			inside = false;
			break;
		}
	}

	if (inside)
		Com_Printf(" [%i]", number);
	else
		Com_Printf(" %i", number);
}

/*
 ==================
 R_AddDrawLight
 ==================
*/
static void R_AddDrawLight (light_t *light, material_t *lightMaterial){

	drawLight_t	*drawLight;

	tr.pc.lights++;

	if (lightMaterial->lightType == LT_GENERIC || lightMaterial->lightType == LT_AMBIENT){
		if (tr.view.numDrawLights == MAX_DRAW_LIGHTS){
			Com_DPrintf(S_COLOR_YELLOW "R_AddDrawLight: MAX_DRAW_LIGHTS hit\n");
			return;
		}

		drawLight = &tr.view.drawLights[tr.view.numDrawLights++];
	}
	else {
		if (tr.view.numDrawFogLights == MAX_DRAW_FOG_LIGHTS){
			Com_DPrintf(S_COLOR_YELLOW "R_AddDrawLight: MAX_DRAW_FOG_LIGHTS hit\n");
			return;
		}

		drawLight = &tr.view.drawFogLights[tr.view.numDrawFogLights++];
	}

	// Copy the light data
	drawLight->data = light->data;

	// Copy the material and the material parms
	drawLight->material = lightMaterial;
	memcpy(drawLight->materialParms, light->l.materialParms, MAX_MATERIAL_PARMS * sizeof(float));

	// Compute scissor rectangle and depth bounds
	R_ClipLightToScreen(drawLight);

	// Generate interaction and shadow lists
	R_GenerateInteractionsList(drawLight);
	R_GenerateShadowsList(drawLight, light->l.noShadows);

	// Development tool
	if (r_showLights->integerValue > 1)
		R_ShowLightVolume(drawLight, light->index);
}

/*
 ==================
 R_CullLight

 Returns true if the light is completely outside the frustum
 ==================
*/
static bool R_CullLight (const odVec3 corners[8]){

	odPlane	*plane;
	bool	clipped = false;
	bool	front, back;
	int		i, j;

	// Check against frustum planes
	for (i = 0, plane = tr.viewParms.frustum; i < 5; i++, plane++){
		front = false;
		back = false;

		for (j = 0; j < 8; j++){
			if (plane->PointOnSide(corners[j]) == PLANESIDE_FRONT)
				front = true;
			else
				back = true;

			if (front && back)
				break;
		}

		if (!front){
			tr.pc.cullOut++;
			return true;
		}

		if (back)
			clipped = true;
	}

	if (clipped)
		tr.pc.cullClip++;
	else
		tr.pc.cullIn++;

	return false;
}

/*
 ==================
 R_AddLights
 ==================
*/
void R_AddLights (void){

	light_t		*light;
	material_t	*lightMaterial;

	if (r_skipLights->integerValue)
		return;

	// Development tool
	if (r_showLights->integerValue > 1)
		Com_Printf("volumes:");

	for (light = tr.scene->activeLight.next; light != &tr.scene->activeLight; light = light->next){
		// Development tool
		if (r_singleLight->integerValue >= 0){
			if (r_singleLight->integerValue != light->index)
				continue;
		}

		// Check for view suppression
		if (!r_skipSuppress->integerValue){
			if (!(light->l.allowInView & tr.viewParms.viewType))
				continue;
		}

		// Check the detail level
		if (light->l.detailLevel > r_lightDetailLevel->integerValue)
			continue;

		// Get the material
		if (light->l.material)
			lightMaterial = light->l.material;
		else {
			if (light->l.type == RL_POINT)
				lightMaterial = tr.defaultPointLightMaterial;
			else
				lightMaterial = tr.defaultProjectedLightMaterial;
		}

		// Set up the light data
		R_SetupLightData(tr.scene, light, lightMaterial, tr.viewParms.primaryView);

		// Check area connection if rendering a primary view
		if (!r_skipVisibility->integerValue && tr.viewParms.primaryView){
			if (lightMaterial->lightType == LT_GENERIC){
				if (light->data.area != -1 && !(tr.areaBits[light->data.area >> 3] & BIT(light->data.area & 7)))
					continue;
			}
		}

		// Cull volume
		if (!r_skipLightCulling->integerValue){
			if (R_CullLight(light->data.corners))
				continue;
		}

		// Mark as visible for this view
		light->viewCount = tr.viewCount;

		if (light->data.precompiled)
			tr.pc.lightsStatic++;
		else
			tr.pc.lightsDynamic++;

		// Add the draw light
		R_AddDrawLight(light, lightMaterial);
	}

	// Development tool
	if (r_showLights->integerValue > 1)
		Com_Printf("\n");
}

/*
 ==================
 R_FreeLightMemory
 ==================
*/
void R_FreeLightMemory (void){

	drawLight_t	*drawLight;
	int			i;

	// Free interaction and shadow lists
	for (i = 0, drawLight = tr.view.drawLights; i < tr.view.numDrawLights; i++, drawLight++){
		if (drawLight->interactionMeshes[0])
			Mem_Free(drawLight->interactionMeshes[0]);
		if (drawLight->interactionMeshes[1])
			Mem_Free(drawLight->interactionMeshes[1]);

		if (drawLight->shadowMeshes[0])
			Mem_Free(drawLight->shadowMeshes[0]);
		if (drawLight->shadowMeshes[1])
			Mem_Free(drawLight->shadowMeshes[1]);
	}

	for (i = 0, drawLight = tr.view.drawFogLights; i < tr.view.numDrawFogLights; i++, drawLight++){
		if (drawLight->interactionMeshes[0])
			Mem_Free(drawLight->interactionMeshes[0]);
	}
}
